package org.lql.algo.codecrush.week002;

/**
 * @author: liangqinglong
 * @date: 2025-07-29 16:26
 * @description: 240. 搜索二维矩阵 II <a href="https://leetcode.cn/problems/search-a-2d-matrix-ii/description/">...</a>
 **/
public class SearchMatrix {

	/**
	 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
	 * <p>
	 * 每行的元素从左到右升序排列。
	 * 每列的元素从上到下升序排列。
	 * <p>
	 * <p>
	 * 示例 1：
	 * <p>
	 * <p>
	 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
	 * 输出：true
	 * 示例 2：
	 * <p>
	 * <p>
	 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
	 * 输出：false
	 * <p>
	 * <p>
	 * 提示：
	 * <p>
	 * m == matrix.length
	 * n == matrix[i].length
	 * 1 <= n, m <= 300
	 * -109 <= matrix[i][j] <= 109
	 * 每行的所有元素从左到右升序排列
	 * 每列的所有元素从上到下升序排列
	 * -109 <= target <= 109
	 */
	public boolean searchMatrix(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;
		int i = 0;
		int j = n - 1;
		while (i < m && j >= 0) {
			if (matrix[i][j] == target) {
				return true;
			} else if (matrix[i][j] > target) {
				j--;
			} else {
				i++;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
		int target = 5;
		SearchMatrix searchMatrix = new SearchMatrix();
		boolean result = searchMatrix.searchMatrix(matrix, target);
		System.out.println(result);
	}
}
